1. Field of the Invention
The present invention relates generally to Low Density Parity Check (LDPC) codes, and in particular, to an LDPC channel code puncturing method for dividing a parity part to be punctured into predetermined groups and assigning different puncturing priorities to the individual groups in order to reduce structural complexity and handle a variation in coding rate while maintaining optimal performance.
2. Description of the Related Art
In general, a digital communication system suffers from errors due to noise, distortion, and interference during data transmission, and commonly uses various algorithms to correct these errors. A 3rd generation (3G) wireless communication system uses convolutional codes for transmission of voice and control signals, and turbo codes for efficient transmission of high-speed data. Turbo codes for transmission of high-speed data are advantageous in that they can obtain a very low bit error rate (BER) at a low signal-to-noise ratio (SNR). However, because the turbo code is high in decoding error rate and decoding complexity and cannot employ a parallel structure, it has a limitation on speed improvement. Therefore, an LDPC code, which has superior performance, lower decoding complexity, and higher decoding rate, due to its possible parallel processing as compared with the turbo code, is now attracting public attention as a code for a 4th generation (4G) mobile communication system.
Although the LDPC code, which is defined as a parity check matrix, for which most elements are ‘0’, was first proposed by Gallager in 1962, it had not been used due to its low practicality in light of the then-technology. However, in 1995, the LDPC code was rediscovered by MacKay and Neal and it was proved that the LDPC code using a Gallager's simple probabilistic decoding technique is very superior in performance.
The LDPC code is defined as a parity check matrix H in which the number of ‘1’s in each row and column is very small, when compared to the number of ‘0’s. The LDPC code is used to determine if a received signal has been subject to normal decoding. That is, if the product of a coded received signal and the parity check matrix becomes ‘0’, it means that there is no reception error. Therefore, for the LDPC code, a predetermined parity check matrix is first designed such that a product of the parity check matrix and all coded received signals becomes ‘0’, and then a coding matrix for coding a transmission signal is inversely calculated according to the determined parity check matrix.
For decoding using the parity check matrix H of the LDPC code, a probabilistic iterative decoding technique is used, using simple parity check equations, and the probabilistic iterative decoding technique finds a codeword that most probabilistically approximates the codeword in which a product of a received signal vector and the parity check matrix satisfies ‘0’.
A sum-product algorithm, which is the typical known decoding method for the LDPC code, finds such a codeword by performing soft-decision iterative decoding using a probability value. That is, the sum-product algorithm determines a codeword designed such that a product of a received signal vector and the parity check matrix satisfies ‘0’ by updating a probability value of each bit using characteristics of a received vector and a channel during every iterative decoding.
Another decoding method for the LDPC code is an algorithm for calculating a transmitted message using a log likelihood ratio (LLR). This algorithm is substantially to the same as the sum-product algorithm, except that an LLR value is used instead of the actual probability value for calculating the transmitted message.
FIG. 1 is a diagram illustrating an exemplary parity check matrix of a simple LDPC code, and FIG. 2 is a diagram illustrating an exemplary factor graph for the parity check matrix of FIG. 1. As illustrated in FIG. 2, the parity check matrix can also be expressed with a factor graph including check nodes, variable nodes (also known as “bit nodes”) and edges for connecting the check nodes to the bit nodes. The use of the expression of the LDPC code through the factor graph can divide a complicated function into simple partial functions, thereby facilitating implementation of the iterative decoding process. That is, the sum-product algorithm is achieved through a process in which a message value delivered through an edge between nodes connected to each other is iteratively updated with a new value in each of the nodes, and one iteration is achieved when a value in each of the nodes is fully updated.
Because a general wireless communication channel is subject to change in channel state with the passage of time, a channel coding system for correcting errors should be able to flexibly vary a coding rate based on channel state information (CSI).
In order to realize the variation in the coding rate, there has been proposed a method for generating codewords having a higher coding rate by using pairs of encoders and decodes optimally designed for a desired coding rate or puncturing a part of the parity in one mother code with a low coding rate. More specifically, there are two possible algorithms capable of generating LDPC codes with various coding rages. A first algorithm designs a parity check matrix suitable for each of coding rates using parity check matrixes having various coding rates according to a predetermined rule. An LDPC code generated with this algorithm is excellent in performance, and its performance for each coding rate can be estimated. However, this algorithm has difficulty in acquiring various coding rates, and cannot be applied to full incremental redundancy (Full IR) or partial incremental redundancy (Partial IR) in a hybrid automatic repeat request (H-ARQ) system in which combining techniques between coded bits are required due to misalignment of a coded bit stream at each coding rate.
A second algorithm performs puncturing according to a coding rate, after a coding process. In this algorithm, a transmitter performs puncturing according to a predetermined pattern, e.g., random puncturing rule, before transmission, and then a decoder in a receiver enables decoding of a punctured bit node using an error correction function of the LDPC code. Accordingly, the known sum-product algorithm can be used. This puncturing algorithm can simply create a desired coding rate, is not subject to change in coding complexity, and supports rate compatibility, i.e., the same puncturing pattern is used at all coding rates, so it can be applied to the H-ARQ technology. However, an LDPC code generated using this algorithm is often inferior to the LDPC code having an optimal parity check matrix at each coding rate. In addition, the LDPC code generated by this algorithm suffers serious change in performance according to random seed value.
Although various puncturing algorithms are being developed in order to prevent performance deterioration due to the puncturing of the LDPC code, there is room for performance improvement and possible implementation when the channel capacity limit or actual application is taken into consideration.